//============================================================================
// Name        : lab3_1.cpp
// Author      : Binda
// Version     :
// Copyright   : Copyright 2011 Binda&Aeolus; All Rights Reserved
// Description : 汽车加油行驶问题（习题3-16）
//问题描述：
//给定一个N*N 的方形网格，设其左上角为起点，坐标为（1，1），X 轴向右为正，Y 轴向下为正，每个方格边长为1。一辆汽车从起点出发驶向右下角终点，其坐标为（N，N）。
//在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：
//（1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。
//（2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。
//（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。
//（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。
//（5）(1)～(4)中的各数N、K、A、B、C均为正整数。
//算法设计：
//求汽车从起点出发到达终点的一条所付费用最少的行驶路线。

//============================================================================
// c[i][j][p]表示由（0，0）到达（i,j）并且剩下汽油可走p段路程的最小代价。
//   则c[i][j][p]=min{c[i+s[q][0]][j+s[q][1]][p+1]+s[q][2]},(q=0,1,2,3);
//   其中，S[4][3]={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};
//

#include <iostream>
#include <FileProcessor.cpp>
using namespace std;

int main() {

	int N, K, A, B, C;

	int c[100][100][12];
	int map[100][100];
	int min;
	int i, j, p, q, x, y, z;
	int s[4][3];
	FileProcessor fp;
	vector<int> data;
	const string infile_name = "input.txt";
	const string outfile_name = "output.txt";
	fp.getdata(infile_name, data);//将文件的数据读入data中
	//Initalization
	N = data[0];
	K = data[1];
	A = data[2];
	B = data[3];
	C = data[4];
	//Output
	cout << "N:" << N << endl;
	cout << "K:" << K << endl;
	cout << "A:" << A << endl;
	cout << "B:" << B << endl;
	cout << "C:" << C << endl << endl;
	//cout<<data.size()<<endl;

	 //方向
	s[0][0] = -1;
	s[0][1] = 0;
	s[0][2] = 0;
	s[1][0] = 0;
	s[1][1] = -1;
	s[1][2] = 0;
	s[2][0] = 1;
	s[2][1] = 0;
	s[2][2] = B;
	s[3][0] = 0;
	s[3][1] = 1;
	s[3][2] = B;

	//Exception Handler
	if (N == 0 || K == 0) {
		cout << "Illegal Input" << endl;
		return 0;
	}
	/*int **map = new int*[N];//网格
	 for (int i = 0; i < N; i++) {
	 map[i] = new int[N];
	 }*/
	//Initialization
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = data[5 + i * N + j];
	//Output
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cout << map[i][j];
		cout << endl;
	}
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			for (z = 0; z <= K + 1; z++)
				c[i][j][z] = 1000000;
	for (z = 0; z <= K; z++)
		c[0][0][z] = 0;
	y = 1;
	while (y != 0) {
		y = 0;
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				if (i != 0 || j != 0) {
					for (p = 0; p < K + 1; p++) {
						min = 1000000;
						for (q = 0; q < 4; q++) {
							if (i == 0 && q == 0)
								continue;
							if (j == 0 && q == 1)
								continue;
							if (i == N - 1 && q == 2)
								continue;
							if (j == N - 1 && q == 3)
								continue;
							if (c[i + s[q][0]][j + s[q][1]][p + 1] + s[q][2]
									< min)
								min = c[i + s[q][0]][j + s[q][1]][p + 1]
										+ s[q][2];
						}
						if (min < 1000000) {
							if (c[i][j][p] > min + A * map[i][j])
								y++;
							c[i][j][p] = min;
							if (map[i][j] == 1) {
								c[i][j][0] += A;
								for (x = 1; x <= K; x++)
									c[i][j][x] = c[i][j][0];
								break;
							}
						} else {
							c[i][j][p] = c[i][j][0] + C + A; //当油用尽但还没到油库时,要建立油库,并且加油,
							for (x = p + 1; x <= K; x++)
								c[i][j][x] = c[i][j][p];
							break;
						}
					}
				}
			}
		}
	}
	printf("%d\n", c[N - 1][N - 1][0]);
	fp.output_data(outfile_name,c[N-1][N-1][0]);
	return 0;
}
